import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class Solution146 {

    int capacity;
    int count;
    Map<Integer,Integer> map1;
    Map<Integer,Integer> map2;
    PriorityQueue<int[]> queue;

    public Solution146(int capacity) {
        count=0;
        this.capacity=capacity;
        map1=new HashMap<>();
        map2=new HashMap<>();
        queue=new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
    }

    public int get(int key) {
        if (map1.containsKey(key)) {
            map2.put(key, count);
            queue.offer(new int[]{key, count});
            count++;
        }
        return map1.getOrDefault(key,-1);
    }

    public void put(int key, int value) {
        if (!map1.containsKey(key) && map1.size()==capacity) {
            while (queue.peek()[1] != map2.get(queue.peek()[0])) {
                queue.poll();
            }
            int k = queue.poll()[0];
            map1.remove(k);
            map2.remove(k);
        }
        map1.put(key,value);
        map2.put(key,count);
        queue.offer(new int[]{key,count});
        count++;
    }

    public static void main(String[] args) {
        Solution146 solution146=new Solution146(2);
        solution146.put(1,1);
        solution146.put(2,2);
        System.out.println(solution146.get(1));
        solution146.put(3,3);
        System.out.println(solution146.get(2));
        solution146.put(4,4);
        System.out.println(solution146.get(1));
        System.out.println(solution146.get(3));
        System.out.println(solution146.get(4));
    }
}
